//一条包含字母 A-Z 的消息通过以下映射进行了 编码 ： 
//
// 
//'A' -> 1
//'B' -> 2
//...
//'Z' -> 26
// 
//
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为： 
//
// 
// "AAJF" ，将消息分组为 (1 1 10 6) 
// "KJF" ，将消息分组为 (11 10 6) 
// 
//
// 注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。 
//
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。 
//
// 题目数据保证答案肯定是一个 32 位 的整数。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "12"
//输出：2
//解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
// 
//
// 示例 2： 
//
// 
//输入：s = "226"
//输出：3
//解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
// 
//
// 示例 3： 
//
// 
//输入：s = "0"
//输出：0
//解释：没有字符映射到以 0 开头的数字。
//含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
//由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
// 
//
// 示例 4： 
//
// 
//输入：s = "06"
//输出：0
//解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 100 
// s 只包含数字，并且可能包含前导零。 
// 
// Related Topics 字符串 动态规划 
// 👍 1018 👎 0

package com.cute.leetcode.editor.cn;
public class DecodeWays {
    public static void main(String[] args) {
        Solution solution = new DecodeWays().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 动态规划
         * dp[i]保存的是以nums[i]结尾的字符串的解码方案数
         * 当前字符可以单独成为解码方案时 dp[i] = dp[i-1]*1
         * 当前字符可以与上一个字符联合组成解码方案时(10-26)dp[i] = dp[i] + dp[i-2]*1
         *
         * 只能由位置 i 的单独作为一个 item，设为 a，转移的前提是 a 的数值范围为 [1,9]，转移逻辑为 f[i] = f[i - 1]
         * 只能由位置 i 的与前一位置（i-1）共同作为一个 item，设为 b，转移的前提是 b 的数值范围为 [10,26]，转移逻辑为 f[i] = f[i - 2]
         * 位置 i 既能作为独立 item 也能与上一位置形成 item，转移逻辑为 f[i] = f[i - 1] + f[i - 2]
         *
         */
        public int numDecodings(String s) {
            int len = s.length();
            if (len == 0 || s.charAt(0) - '0' == 0) return 0;
            char[] chars = s.toCharArray();
            int[] dp = new int[len];
            dp[0] = 1;// 初始化
            for (int i = 1; i < len ; i++) {
                if (chars[i]!='0') dp[i] = dp[i-1];//这里表明可以单独解码，所以方案数至少和前一个位置相等
                int num = chars[i] - '0' + (chars[i-1] - '0') * 10;
                if (num >= 10 && num <= 26) {
                    if (i == 1) dp[i]++;
                    else dp[i] += dp[i-2];//如果和上一个位置能组上，需要再加上i-2位置处的个数
                }
            }
            return dp[len-1];
        }

        /**
         * 二刷的时候被恶心到了，关于0进行了区分
         * 还是得使用dp来做，方便很多
         */
        public int numDecodings2(String s) {
            if(s.charAt(0) == '0') return 0;
            int[] dp = new int[s.length()];
            dp[0] = 1;
            for (int i = 1; i < s.length(); i++){
                if (s.charAt(i) == '0') {// 当前值为0时，必须考虑前一个值
                    // 前一个值不合适，直接返回0
                    if (s.charAt(i - 1) > '2' || s.charAt(i - 1) == '0') return 0;
                    else{
                        // 必须绑定前一个值才行
                        if (i > 1) dp[i] = dp[i - 2];
                        else dp[i] = 1;
                    }
                }else{// 当前值不为0的时候
                    // 如果前一个值为0则等于前值即可
                    if (s.charAt(i - 1) == '0') dp[i] = dp[i - 1];
                    else{
                        // 这里我的判断是麻烦了一些，一刷时先统一赋值了一下
                        if (Integer.parseInt(s.substring(i - 1, i + 1)) <= 26 ){// 这表示可以联合使用
                            if (i > 1) dp[i] = dp[i - 1] + dp[i - 2];
                            else dp[i] = 2;
                        } else dp[i] = dp[i - 1];// 这里表示只能单独使用
                    }
                }
            }
            return dp[s.length() - 1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}



























